package com.ting.test.algorithms.大厂刷题班;

import java.util.Arrays;

/**
 * 给定一个正整数数组arr代表每个人的体重
 * 给定一个limit代表船的最大载重
 * 每艘船最多做2人，且不能超重
 * 求让suo所有的人都能过河并且使用的船最少的方案
 */
public class 最多装两个人的船同时过河的问题 {
    public static void main(String[] args) {
        int[] arr = new int[]{4, 2, 5, 2, 1, 9, 8, 10, 7, 3};
        int limit = 10;
        int count = process(arr, limit);
    }

    private static int process(int[] arr, int limit) {

        for (int num : arr) {
            if (num > limit) {
                return 0;//如果有一个人的体重超过了船的最大载重，那么无论如何也不可能把所有人都过河
            }
        }

        Arrays.sort(arr);//排序

        int midLimit = limit / 2;//确定船载重的中位数

        int L = 0;
        int R = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > midLimit) {
                L = i;
                R = i + 1;
                break;
            }
        }

        int[] flagArr = new int[arr.length];
        while (L >= 0 && R < arr.length) {
            if (arr[L] + arr[R] <= limit) {
                //如果当前L+R能够满足载重 则将R往前推 直到不能满足为止
                for (int i = R + 1; i < arr.length; i++) {
                    if (arr[L] + arr[i] <= limit) {
                        R++;
//                        flagArr[R];
                    } else {

                    }
                }


            }

        }
        return 0;
    }
}
